package com.leetcode.math;

import java.util.*;

public class TopKFrequent {
    public static void main(String[] args) {

    }

    public int[] topKFrequent(int[] nums, int k) {
        int[] res = new int[k];
        Map<Integer, Integer> freqMap = new HashMap<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1);
        }
        PriorityQueue<int[]> queue = new PriorityQueue<>((a,b)-> a[1] - b[1]);
        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            int num = entry.getKey();
            int freq = entry.getValue();
            if (queue.size() == k) {
                if (freq > queue.peek()[1]) {
                    queue.poll();
                    queue.offer(new int[]{num, freq});
                }
            } else {
                queue.offer(new int[]{num, freq});
            }
        }
        for (int i = 0; i < k; i++) {
            res[i] = queue.poll()[0];
        }
        return res;
    }
}
